class Solution {
    vector<vector<long long>> memo;
    long long dfs(int i, int j, vector<int>& A, vector<int>& B)
    {
        // 因为是从后往前考虑，所以当 i 等于 0 时还需要喝饮料
        if(i < 0)
            return 0;
        // 1. 继续喝当前种类的饮料
        // 2. 换另一种饮料喝
        if(memo[i][j] != -1)
            return memo[i][j];
        return memo[i][j] = max(dfs(i - 1, j, A, B), dfs(i - 2, j ^ 1, A, B)) + (j == 0 ? A[i] : B[i]);
    }
public:
    long long maxEnergyBoost(vector<int>& A, vector<int>& B) {
        // 使用DP解法(单纯DP时间复杂度过不了，需要使用记忆化搜索)
        // dfs(i, j)表示第 i 个小时喝 j 种饮料所能获得的最大能量
        // j 是 0 表示正在和 A 饮料，j 是 1 表示正在喝 B 饮料
        int n = A.size();

        // memo数组初始化为 -1
        memo = vector<vector<long long>>(n, vector<long long>(2, -1));
        return max(dfs(n - 1, 0, A, B), dfs(n - 1, 1, A, B));
    }
};